import com.sun.xml.internal.ws.api.model.CheckedException;

import java.util.*;

/**
 *  1: 反转链表
 * 2:两数相加
 * 3:删除链表的倒数第 N 个结点
 * 4：合并两个有序链表
 *5：合并K个升序链表
 * 6:两两交换链表中的节点
 * 7： K 个一组翻转链表
 * 8：旋转链表
 */


public class Solution {
    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode head;
    public void createLink() {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(4);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(2);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4; /* */
        head = listNode1;
    }
  /*1: 反转链表
    给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    My:头插法*/
  public ListNode My_reverseList(ListNode head) {
      //如果头结点为空返回空
      if (head==null)return null;
      ListNode cur=head.next;
      head.next=null;
      while (cur!=null){
          ListNode tmp=cur.next;
          cur.next=head;
          head=cur;
          cur=tmp;
      }
      return head;
  }
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;//存储头结点
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    /*2:两数相加
    给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
    请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
        My:将俩个链表反转后按照进位相加
     */

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;//head为当前节点，tail用来循环
        int carry = 0;//用来存放进位
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
//            尾插法
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
    /* 3:删除链表的倒数第 N 个结点
    * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
    * My：快慢指针*/
    public ListNode My_removeNthFromEnd(ListNode head, int n) {
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode fast=head;
        ListNode slow=head;
        ListNode pre=res;
        while (n>0){
            fast=fast.next;
            n--;
        }
        while (fast!=null){
            fast=fast.next;
            pre=slow;
            slow=slow.next;
        }
        pre.next=slow.next;
        return res.next;
    }
    /*一种容易想到的方法是，我们首先从头节点开始对链表进行一次遍历，得到链表的长度 L。
    随后我们再从头节点开始对链表进行一次遍历，当遍历到第 L−n+1个节点时，它就是我们需要删除的节点。
    */

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
    /*我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 nnn 个节点就是需要删除的节点，
    并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。*/
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);//创建头结点前一个
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
    /*4：合并两个有序链表
    * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    * My:与合并数组一致 */

    public ListNode My_mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead;
        ListNode tmp;

        if (list1 ==null)return list2;
        if (list2 == null)return  list1;
//        将特殊情况排除
//        先赋予新的头结点
        if (list1.val <= list2.val){
            newHead=list1;
            tmp=list1;
            list1= list1.next;
        }else{
            newHead=list2;
            tmp=list2;
            list2= list2.next;
        }
        while (list1 !=null && list2 !=null){
            if (list1.val <= list2.val){
                tmp.next=list1;
                list1= list1.next;
                tmp=tmp.next;

            }else{
                tmp.next=list2;
                list2= list2.next;
                tmp=tmp.next;
            }
        }
        if (list1 !=null)tmp.next=list1;
        if (list2 !=null)tmp.next=list2;

        return newHead;
    }
//    官方优化过后的代码
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
    //递归的方式
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    /*5：合并K个升序链表
     给你一个链表数组，每个链表都已经按升序排列。
    请你将所有链表合并到一个升序链表中，返回合并后的链表。
    My:通过不断调用合并俩个链表解决*/
    public ListNode My_mergeKLists(ListNode[] lists) {
        ListNode res=null;
        for (int i = 0; i < lists.length; i++) {
            res=mergeTwoLists(res,lists[i]);
        }
        return res;
    }
    //优化思路：利用分治的思想
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) /2;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    /*6:两两交换链表中的节点
    给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
    你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
    My:让链表一次性走俩步*/

    public ListNode My_swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }


//    官方——递归的方式，交换节点
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }

    /*7： K 个一组翻转链表
    * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
    k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，
    * 那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
    * My:确定反转区间利用反转链表，循环完成
    * */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);//创建前一个节点
        dummy.next = head;

        ListNode pre = dummy;//确定K个节点一组的链表的前一个节点
        ListNode end = dummy;//定K个节点一组的链表的尾节点

        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++) end = end.next;//确定尾节点的位置
            if (end == null) break;
            ListNode start = pre.next;//k组链表的头结点,同时start指向了待会反转完的尾节点
            ListNode next = end.next;//记录尾节点之后的位置，为续上链表做准备
            end.next = null;//断开链表
            pre.next = reverse(start);//重新链接链表
            start.next = next;//续上链表
            pre = start;//移动pre指向反转完的尾节点

            end = pre;//同上，继续进行下一次
        }
        return dummy.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
    public int legth(ListNode head){
        int count=0;
        while (head!=null){
            count++;
            head= head.next;
        }
        return count;
    }
    //数组向右移动k个位置
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }
    /*8：旋转链表
    * 你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
    * My:利用数组实现*/
    public ListNode My_rotateRight(ListNode head, int k) {
        if (head==null)return null;
        int[] array=new int[legth(head)];
        ListNode cur=head;
        for (int i = 0; i < array.length; i++) {
            array[i]=cur.val;
            cur=cur.next;
        }
        rotate(array,k);
        cur=head;
        for (int i = 0; i < array.length; i++) {
            cur.val=array[i];
            cur=cur.next;
        }
        return head;

    }
    //闭合为环移动，然后我们找到新链表的最后一个节点（即原链表的第 (n−1)−(kmodn)个节点），
    // 将当前闭合为环的链表断开.即可得到我们所需要的结果

    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;//链表长度为n
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        int add = n - k % n;//判断k是否是链表长度的整数倍
        if (add == n) {
            return head;// k为n的倍数时，新链表将与原链表相同
        }
        iter.next = head;//闭合为环
        //新链表的最后一个节点为原链表的第 (n−1)−(kmodn) 个节点（从0开始计数）
        while (add-- > 0) {
            iter = iter.next;
        }
        ListNode ret = iter.next;
        iter.next = null;
        return ret;
    }
    /*9：删除排序链表中的重复元素 II
    * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，
    * 只留下不同的数字 。返回 已排序的链表 。
    *My:增加一个表头，遍历链表，如果遇到了相同节点就修改链表将所有相同的节点都跳过*/

    public ListNode deleteDuplicates2 (ListNode head) {
        //空链表
        if(head == null)
            return null;
        ListNode res = new ListNode(0);
        //在链表前加一个表头
        res.next = head;
        ListNode cur = res;
        while(cur.next != null && cur.next.next != null){
            //遇到相邻两个节点值相同
            if(cur.next.val == cur.next.next.val){
                int temp = cur.next.val;
                //将所有相同的都跳过
                while (cur.next != null && cur.next.val == temp)
                    cur.next = cur.next.next;
            }
            else
                cur = cur.next;
        }
        //返回时去掉表头
        return res.next;
    }
    /*9删除排序链表中的重复元素
    * 给定一个已排序的链表的头 head，删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。*/
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
    /*10：分隔链表
    * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
    * 使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
    * my:不要吝啬变量的使用，官方第一个也是这种解法*/
    public ListNode my_partition(ListNode head, int x) {
        ListNode tmp1=new ListNode(-1);
        ListNode tmp2=new ListNode(-1);
        ListNode cur=head;
        ListNode pre=tmp1;
        ListNode pre2=tmp2;
        while (cur!=null){
            if (cur.val<x){
                tmp1.next=cur;
                tmp1= tmp1.next;
                cur=cur.next;
                tmp1.next=null;
            }else {
              tmp2.next=cur;
              tmp2=tmp2.next;
              cur=cur.next;
              tmp2.next=null;
            }
        }
        tmp1.next=pre2.next;
        return pre.next;
    }

   /*11：反转链表 II
   * 给你单链表的头指针 head 和两个整数 left 和 right ，
   * 其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
   * my:记录left的前一个节点，与right的后一个节点，然后将left——right这段空间反转，在续上链表*/
   public ListNode My_reverseBetween(ListNode head, int left, int right) {
        ListNode cur=head;
        ListNode start;//指向开始的节点
        ListNode end;//指向结束的节点
       ListNode pre=new ListNode(-1);//创建一个新节点，防止反转第一个节点
       pre.next=head;
       ListNode newhead=pre;
       while (left-1>0){
           cur=cur.next;
           pre=pre.next;
           right--;
           left--;
       }
       start=cur;
       while (right-1>0){
           cur=cur.next;
           right--;
       }
       end=cur.next;//
       cur.next=null;//断开链表
       pre.next=reverseList(start);//将反转后的链表续上
       start.next=end;
       return newhead.next;
   }
   /*12: 复制带随机指针的链表,在Solution2中解决
   * */
    /*13：重排链表
    给定一个单链表 L 的头节点 head ，单链表 L 表示为：
    My：先找到中间节点,然后反转中间节点以后得节点，最后将反转后得链表插入到原来得链表中
    */
   public void My_reorderList(ListNode head) {
       if (head==null)return;
       int mid=legth(head)/2;
       ListNode end;
       ListNode cur=head;
       //找到中间节点
       while (mid>0){
           cur=cur.next;
           mid--;
       }
       end=cur.next;//
       cur.next=null;//断开链表
       end=reverseList(end);//反转链表

       cur=head;
       while (end!=null){
           ListNode tmp=end.next;
           end.next=cur.next;
           cur.next=end;
           end=tmp;
           cur=cur.next.next;
       }
   }

    //官方，利用线性表存储，然后利用下标改变
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> list = new ArrayList<ListNode>();
        ListNode node = head;
        while (node != null) {
            list.add(node);
            node = node.next;
        }
        int i = 0, j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }
    /*14：LRU 缓存，在LRUCache中*/
    /*15： 对链表进行插入排序
    给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头*/
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(0);//创建一个新的头结点
        dummyHead.next = head;
        //lastSorted为已排序的最后一个节点，curr为遍历链表
        ListNode lastSorted = head, curr = head.next;
        while (curr != null) {
            //说明有序将astSorted后移即可
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;
            } else {
                //找到插入合适位置插入
                ListNode prev = dummyHead;
                while (prev.next.val <= curr.val) {
                    prev = prev.next;
                }
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next;
        }
        return dummyHead.next;
    }
    /* 16：回文链表
    * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。*/

    public boolean isPalindrome(ListNode head) {
        if (head==null)return true;

        int mid=legth(head)/2;
        ListNode cur=head;
        while (mid>0){
            cur=cur.next;
            mid--;
        }
        cur=reverseList(cur);
        ListNode q = head;
        while(cur != null){
            //比较判断节点值是否相等
            if(cur.val != q.val)
                return false;
            cur = cur.next;
            q = q.next;
        }
        return true;
    }
   /* 17:删除链表中的节点
   * 给你一个需要删除的节点 node 。你将 无法访问 第一个节点  head。
   * my:不让删除自己，那就等于下一个值，并且删除下一个节点*/
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
    /* 18：奇偶链表
    * 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。*/
    public ListNode oddEvenList (ListNode head) {
        if (head == null){
            return null;
        }
        if (head.next == null){
            return  head;
        }
        ListNode p=head;
        int n=1;
        ListNode Js=new ListNode(-1);
        ListNode Os=new ListNode(-1);
        ListNode cur = Js;
        ListNode cur1 = Os;
        while (p!=null){

            if (n%2!=0){
                ListNode listNode = new ListNode(p.val);
                cur.next = listNode;
                cur=listNode;
            } else{
                ListNode listNode = new ListNode(p.val);
                cur1.next = listNode;
                cur1=listNode;
            }
            p=p.next;
            n++;
        }
        p=Js;
        while (p.next!=null){
            p=p.next;
        }
        p.next=Os.next;
        return Js.next;
    }
    /*19：俩数相加*/
    public ListNode addTwoNumbers2 (ListNode head1, ListNode head2) {
        // 进行判空处理
        if(head1 == null)
            return head2;
        if(head2 == null){
            return head1;
        }
        // 反转h1链表
        head1 = reverse(head1);
        // 反转h2链表
        head2 = reverse(head2);
        // 创建新的链表头节点
        ListNode head = new ListNode(-1);
        ListNode nHead = head;
        // 记录进位的数值
        int tmp = 0;
        while(head1 != null || head2 != null){
            // val用来累加此时的数值（加数+加数+上一位的进位=当前总的数值）
            int val = tmp;
            // 当节点不为空的时候，则需要加上当前节点的值
            if (head1 != null) {
                val += head1.val;
                head1 = head1.next;
            }
            // 当节点不为空的时候，则需要加上当前节点的值
            if (head2 != null) {
                val += head2.val;
                head2 = head2.next;
            }
            // 求出进位
            tmp = val/10;
            // 进位后剩下的数值即为当前节点的数值
            nHead.next = new ListNode(val%10);
            // 下一个节点
            nHead = nHead.next;

        }
        // 最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位
        if(tmp > 0){
            nHead.next = new ListNode(tmp);
        }
        // 重新反转回来返回
        return reverse(head.next);
    }

}